COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\input macro[1,mps]
C00019 ENDMK
C⊗;
\input macro[1,mps]
\input macrwf[1,mps]
\magnification\magstephalf
\baselineskip 14pt
\leftline{\sevenrm A99.Tex[254,rwf]\today}
\leftline{\copyright\sevenrm Robert W. Floyd, December 1, 1989}
\leftline{\sevenrm Unpublished draft}
\bigskip
\noindent{\bf Notes on NP-Completeness.\hfill}

A locally constrained symbol system (LCSS) consists of a finite set
{\bf V} of variables ($\left|{\bf V}\right|=v$) over a finite 
alphabet~$\Sigma$ ($\left|\Sigma\right|=s$) which we may, if we choose,
consider as the numbers from 1 to~$s$. Constraints are imposed as
relations on certain subsets of the variables; there is a fixed 
bound~$b$ on the number of variables in a constrained subset, so the
number of constraints is at most $\sum↓{i=1}↑k{v\choose i}$, a~polynomial
in~$v$. Often, we want to know if there is a mapping ${\bf V}→\Sigma$
satisfying all the constraints. There are $s↑v$ such mappings, so
enumerating them takes time exponential in~$v$, but for each one,
the number of constraints to check is polynomial in~$v$.

With any LCSS $U$ we may associate a well-formed formula $W$ of the
propositional calculus. We use as variables $x↓{ij}$
($1≤i≤v$, $1≤j≤s$); we will construct~$W$ so that if~$W$ is satisfiable
at all, $U$~is satisfiable, and letting $x↓{ij}≡(V↓i=j)$ satisfies~$W$.
That is, $x↓{ij}$~more or less represents the proposition that $V↓i$~has
the value~$j$.

The clauses of $W$ are

\disleft 20pt:(1):
For each $1≤i≤v$,

\display 40pt::
$x↓{i1}∨x↓{i2}∨\ldots ∨x↓{is}$

\disleft 20pt:(2):
For each relation $R(V↓{i↓1},V↓{i↓2},\ldots,V↓{i↓b})$,
and for each element $\langle\sigma↓1,\sigma↓2,\ldots,\sigma↓b\rangle$
of $\Sigma↑b∧{\bar R}$,

\display 40pt::
$\overline{x↓{i↓1,\sigma↓1}}∨\overline{x↓{i↓2,\sigma↓2}}∨\ldots ∨
\overline{x↓{i↓b,\sigma↓b}}$.

Clearly any assignment of values in $\Sigma$ to each of the variables
of~$U$ that satisfies the constraints will satisfy each of the above
clauses, and therefore the conjunction~$W$ of the clauses.

Conversely, if there is a model $M$ for $W$ (that is, an assignment
of truth values to the $\{x↓{ij}\}$ satisfying~$W$), for each~$i$
we pick some~$j↓i$ such that $x↓{i,j↓i}$ is true in~$M$ and let
$V↓i=j↓i$. If this violated some relation, say $R(V↓1,V↓2,V↓3)$, we 
would have $\langle j↓1,j↓2,j↓3\rangle\in{\bar R}$, and the clause
$\overline{X↓{1,j↓1}}∨
\overline{X↓{2,j↓2}}∨
\overline{X↓{3,j↓3}}$ would not be satisfied by~$M$. Therefore,
the satisfiability of~$W$ implies that of~$U$.

{\rmn
{\narrower\smallskip\noindent
{\bf Example.} Fermat's last theorem.

For given $m$, $n$, consider whether $a↑n+b↑n=c↑n$ is solvable in
positive integers $a,b,c≤m$. We formulate this as a LCSS by designing
a form (or circuit diagram) into which can be filled
the digits of the computation testing
whether $a↑n+b↑n=c↑n$. Since $x↑n$ can be computed in
$O(\log n)$ multiplications, each of size at most $(n\lg x)↑2$ bits,
the number of variables is
$$O\bigl(\lg n(n\lg m)↑2\bigr)\,.$$
\vfill\eject
\noindent
{\bf Example.}

Consider whether a given nondeterministic Turing machine accepts a string~$x$
in time~$t$. If so, there is an accepting computation, which can be
written as a $(t+1)\times (t+1)$ array of symbols, with each row a machine
configuration. Local constraints require the top row to be the initial
configuration of the machine on input~$x$ (say, 
$\vdash x\hbox{\tt\spa}*\,\dashv$), require each symbol on subsequent lines to be
consistent with those above and beside it; and require the last line
to be in an accepting state (by banning all other control states).

If $t$ is a polynomial in the length of~$x$, the number of
variables in the above LCSS is bounded by a polynomial in the length
of~$x$, and the associated satisfiability problem in the propositional
calculus is bounded in size by a polynomial in the length of~$x$. Thus
any problem in~NP is reducible to a satisfiability problem in the
propositional calculus. Since SAT is clearly in~NP, it is NP-complete.

\noindent
{\bf Example.}

Given any finite mathematical domain~$D$, take a mathematical formula~$F$
over that domain. We want to know if $F$ can take on a particular value
$d\in D$. Construct an LCSS, $U$, using as variables the variables of~$F$
and the values of the non-atomic subexpressions of~$F$. If $F$~contains
a subexpression $e↓1=g(e↓2,e↓3)$, the
requirement $V↓1=g(V↓2,V↓3)$ is a local constraint, as is the requirement
that $V↓F=d$. Any such question then reduces to a satisfiability problem
in clause form.

In particular, if $D$ is $\{$true, false$\}$, we see that any satisfiability
problem in predicate calculus is reducible to a satisfiability problem
in clause form with all clauses of length $≤3$. If we want all clause
lengths to be exactly~3, we can replace shorter ones, introducing new
variables, by
$$\eqalign{x&≡(x∨y∨z)∧(x∨y∨{\bar z}∧(x∨{\bar y}∨z)∧(x∨{\bar y}∨{\bar z})\cr
x∨y&≡(x∨y∨z)∧(x∨y∨{\bar z})\,.\cr}$$
\smallskip}
}

\medskip\noindent
{\bf The $k$-clique problem is NP-complete.}

The $k$-clique problem asks whether a given graph contains a complete
subgraph of size~$k$. It is clearly in~NP. We show that any satisfiability
problem, for a wff~$W$ in the propositional calculus, is reducible
to a $k$-clique problem, where $k$ is the number of distinct variables
plus the number of operators (i.e., the number of non-atomic subexpressions)
in~$W$. From~$W$, we construct graph~$G$, of which the nodes are propositions
of two forms:

\smallskip
\display 40pt:(A):Variable $X$ is (true)/(false).

\smallskip
\display 40pt:(B):Subexpressions $E↓1$, $E↓2$, $E↓3$ are respectively
(true)/(false), (true)/(false), (true)/(false), 

\smallskip
\noindent
where $E↓1=f(E↓2,E↓3)$ and the three truth values $\tau↓1$, $\tau↓2$, $\tau↓3$
satisfy $\tau↓1=f(\tau↓2,\tau↓3)$. Further, if $E↓1=W$, we require
$\tau↓1={\rm true}$.

The edges of graph $G$ are all pairs of nodes which do not {\it explicitly\/}
contradict each other (by asserting distinct truth values for the same
formula). Examples of non-edges:

\smallskip
\display 40pt::
($X$ is true, $X$ is false).

\smallskip
\display 40pt::
($E↓1$, $E↓2$, $E↓3$ are respectively $T$, $F$, $F$; $E↓1$, $E↓2$, $E↓3$
are respectively $T$, $T$, $F$).

\smallskip
\display 40pt::
$\bigl(E↓1∧(E↓2∨E↓3)$, $E↓1$, $(E↓2∨E↓3)$ are respectively $F$, $T$, $F$;
$E↓2∨E↓3$, $E↓2$, $E↓3$ are respectively $T$, $T$, $T\bigr)$.

\smallskip
\noindent
Any clique can contain at most as many nodes of type (A) as there are
distinct variables, and as many of type~(B) as there are operators,
in~$W$. A~clique containing this many nodes assigns truth values
in such a way as to satisfy~$W$, reducing the satisfiability of~$W$ to a
$k$-clique problem.

{\rmn
{\narrower\smallskip\noindent
{\bf Example.} 

A 5-clique problem from $p∧\neg(q⊃p)$.

\figbox 4.0truein:

\noindent
Since no two nodes on the same level are linked, any 5-clique must contain
one node on each level. We must pick these nodes:
$$\eqalign{&\bigl(p,\neg(q⊃p),p∧\neg(q⊃p)\bigr)\cr
&\bigl(\overline{q⊃p},\neg(q⊃p)\bigr)\cr}$$
but now there is no legal choice in the third level, so $p∧\neg(q⊃p)$ is
unsatisfiable.
\smallskip}
}

\medskip\noindent
{\bf Set Covering is NP-complete.}

\medskip\noindent
{\bf Proof.} Set covering is clearly in NP. Given a satisfiability problem~$C$
in $n$~variables as a set of clauses, we add to it the clauses $x∨\neg x$
for each variable~$x$, without affecting satisfiability. For each literal~$L$,
let $S↓L$ be the set of clauses containing~$L$. Because of the added clauses,
any covering of the clauses must include $n$~sets. A~covering with exactly
$n$~sets selects exactly one of~$X$ and $\neg X$ for each variable~$X$, and
makes each clause true, thereby satisfying~$C$, so the satisfiability
problem in clause form is reducible to the set covering problem.

{\rmn
{\narrower\smallskip\noindent
{\bf Example.} 
{\obeylines\smallskip
\qquad $C$:\phantom{ add }$\,(X)$, $(\bar{X}∨Y)$, $({\bar X}∨{\bar Y})$;
\qquad\phantom{$C$: }add $(X∨{\bar X})$, $(Y∨{\bar Y})$
\smallskip}

\figbox 2.5truein:

\noindent
There is no 2-covering, so
$$X∧({\bar X}∨Y)∧({\bar X}∨{\bar Y})\;{\rm is\; unsatisfiable.}$$
\smallskip}
}

An example of a set covering problem:
given a set of cookbooks, is there a subset of a given size that includes
every recipe?

An example of a $k$-clique problem: our dinner table seats ten guests.
Can we plan a party for ten of our friends without including any two who
can't stand the sight of each other?

\medskip\noindent
{\bf Vertex Cover is NP-complete.}

Given wff $W$ with variables ${\bf V}=\{V↓j\}$, $\left|{\bf V}\right|=v$,
and clauses ${\bf C}=\{C↓i\}$, $\left|{\bf C}\right|=c$.
Construct graph~$G$ with nodes including:

\smallskip
\disleft 20pt:(1):
all literals $L$ over $V$;

\smallskip
\disleft 20pt:(2):
all $\langle L,C\rangle$ where $L$ is a literal of $C$;

\smallskip
\noindent
and all edges $(L,{\bar L})$, $(\langle L,C\rangle,\langle L',C\rangle)$
($L≠L'$), and $(L,\langle L,C\rangle)$. The first set of edges requires
that the cover contain at least $v$~literals. The second requires that
for clause~$C↓i$, the cover contain (any) $\left|C↓i\right|-1$ nodes of
the form $\langle L,C↓i\rangle$. In order for the vertex cover to  require
no more nodes, for each clause $C↓i$ where the cover omits $\langle L,C↓i\rangle$,
it must include~$L$, where $L⊃C↓i$. Thus the literals included satisfy~$W$.
Conversely, any model for~$W$ readily yields a vertex cover for~$G$, omitting
one $\langle L,C↓i\rangle$ such that $L⊃C↓i$ for each clause.
\bye